/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class RestoreIPAddresses {

	/**
	Given a string containing only digits, restore it by returning all possible valid IP address combinations.

	For example:
	Given "25525511135",

	return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
	 */
	public ArrayList<String> restoreIpAddresses(String s) {
		ArrayList<String> ips = new ArrayList<String>();
		if (s == null || s.isEmpty() || s.length() > 12) {
			return ips;
		}

		restoreIpAddressesHelp(s, 0, 0, new StringBuffer(), ips);
		//restoreIpAddressesHelp(s, 0, 0, "", ips);
		return ips;
	}

	/**
	 * 
	 * @param s, stirng containing number
	 * @param index, current index in s
	 * @param counter, the number of sub ip 
	 * @param buffer,
	 * @param ips
	 */
	private void restoreIpAddressesHelp(String s, int index, int counter,
			String buffer, ArrayList<String> ips) {

		if (s.length() - index > (4 - counter) * 3)
			return;
		if (s.length() - index < (4 - counter))
			return;

		if (index == s.length() && counter == 4) {
			ips.add(buffer.substring(0, buffer.length() - 1));
			return;
		}

		int num = 0;
		for (int i = index; i < s.length() && i <= index + 2; i++) {
			num = num * 10 + (s.charAt(i) - '0');
			if (num <= 255) {
				buffer = buffer + s.charAt(i);
				restoreIpAddressesHelp(s, i + 1, counter + 1, buffer + '.', ips);
			}
			if (num == 0) {// to avoid 010.0.2.3
				break;
			}
		}
	}

	private void restoreIpAddressesHelp(String s, int index, int counter,
			StringBuffer buffer, ArrayList<String> ips) {

		if (s.length() - index > (4 - counter) * 3)
			return;
		if (s.length() - index < (4 - counter))
			return;

		if (index == s.length() && counter == 4) {
			ips.add(buffer.substring(0, buffer.length() - 1));
			return;
		}

		int num = 0;
		for (int i = index; i < s.length() && i <= index + 2; i++) {
			num = num * 10 + (s.charAt(i) - '0');
			if (num <= 255) {
				buffer.append(s.charAt(i));
				int buffSize = buffer.length();
				restoreIpAddressesHelp(s, i + 1, counter + 1,
						buffer.append('.'), ips);
				buffer.setLength(buffSize);
			}
			if (num == 0) {// to avoid 010.0.2.3
				break;
			}
		}
	}

	/*
	vector<string> restoreIpAddresses(string s) {   
	        vector<string> col;   
	        string ip;   
	        partitionIP(s, 0, 0, ip, col);   
	        return col;   
	   }   
	   void partitionIP(string s, int startIndex, int partNum,    
	   string resultIp, vector<string>& col)   
	   {   
	        //max: 3 bits per partition   
	        if(s.size() - startIndex > (4-partNum)*3) return;   
	        //min: 1 bit per partition   
	        if(s.size() - startIndex < (4-partNum)) return;  
	        if(startIndex == s.size() && partNum ==4)   
	        {   
	             resultIp.resize(resultIp.size()-1);   
	             col.push_back(resultIp);   
	             return;   
	        }   
	        int num =0;   
	        for(int i = startIndex; i< startIndex +3; i++)   
	        {   
	             num = num*10 + (s[i]-'0');   
	             if(num<=255)   
	             {   
	                  resultIp+=s[i];   
	                  partitionIP(s, i+1, partNum+1, resultIp+'.', col);       
	             }    
	             if(num ==0)//0.0.0.0 valid, but need to avoid 0.1.010.01   
	             {   
	                  break;   
	             }   
	        }   
	   }   
	*/

	/**
	 * 
	 */
	public RestoreIPAddresses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		RestoreIPAddresses ripa = new RestoreIPAddresses();
		String s = "010010";
		ArrayList<String> ips = ripa.restoreIpAddresses(s);

		for (String ip : ips) {
			System.out.println(ip);
		}
	}

}
